#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
using namespace std;


//Definition for singly-linked list.
struct ListNode {
	int val;
	ListNode* next;
	ListNode()
		: val(0)
		, next(nullptr)
	{}
	ListNode(int x)
		: val(x)
		, next(nullptr)
	{}
	ListNode(int x, ListNode* next)
		: val(x)
		, next(next)
	{}
};

class Solution {
public:
	ListNode* reverseList(ListNode* head) {
		ListNode* temp;
		ListNode* cur = head;
		ListNode* pre = NULL;
		while (cur) {
			temp = cur->next;
			cur->next = pre;
			pre = cur;
			cur = temp;
		}
		return pre;
	}
};

class Solution {
public:
	ListNode* reverseList(ListNode* head) {
		if (head == NULL)  return NULL;
		if (head->next == NULL) return head;

		ListNode* last = reverseList(head->next);
		head->next->next = head;
		head->next = NULL;
		return last;
	}
};

class Solution {
public:
	ListNode* reverse(ListNode* pre,ListNode* cur) {
		if (cur == NULL) return pre;
		ListNode* temp = cur->next;
		cur->next = pre;
		return reverse(cur, temp);
	}
	ListNode* reverseList(ListNode* head) {
		return reverse(NULL, head);
	}
};


